package com.kehao.newcoder;

import org.junit.Test;

public class NC35Solution {
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        rc = Math.min(ic+dc,rc);
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        dp[0][0] = 0;
        dp[0][1] = ic;
        dp[1][0] = dc;
        dp[1][1] = str1.charAt(0) == str2.charAt(0)?0:rc;
        for (int i = 1; i < str1.length()+1; i++) {
            dp[i][0] = dp[i-1][0] + dc;
        }
        for (int i = 1; i < str2.length()+1; i++) {
            dp[0][i] = dp[0][i-1] + ic;
        }
        for (int i = 1; i < str1.length() + 1; i++) {
            for (int j = 1; j < str2.length() + 1; j++) {
                int value1 = ic + dp[i-1][j];
                int value2 = dc + dp[i][j-1];
                int value3 = dp[i-1][j-1]+(str1.charAt(i-1) == str2.charAt(j-1)?0:rc);
                int min = Math.min(value1,value2);
                min = Math.min(value3,min);
                dp[i][j] = min;
            }
        }
        return dp[str1.length()][str2.length()];
    }

    @Test
    public void test01(){
        System.out.println(minEditCost("abc", "adc", 5, 3, 2));
    }
}
